package com.dmall.algorithm.chapter01;

import java.util.Stack;

/**
 * 不用暴力解法，使用栈这样的一个数据结构
 * 时间复杂度为O(n)
 */
public class Leetcode84V3 {

    private static class Pairs {
        private int index;
        private int height;

        public Pairs(int index, int height) {
            this.index = index;
            this.height = height;
        }

        public int getIndex() {
            return index;
        }

        public int getHeight() {
            return height;
        }
    }

    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        if (heights.length == 1) {
            return heights[0];
        }

        Stack<Pairs> stack = new Stack<>();
        stack.push(new Pairs(-1, -1));
        int maxArea = 0;
        int i = 0;
        for (; i < heights.length; i++) {
            int height = heights[i];
            Pairs peek = stack.peek();
            if (height < peek.getHeight()) {
                while (stack.peek().getHeight() > height) {
                    peek = stack.peek();
                    stack.pop();
                    Pairs prev = stack.peek();
                    int curArea = peek.height * (i - prev.index - 1);
                    maxArea = Math.max(maxArea, curArea);
                }
            }
            stack.push(new Pairs(i, height));
        }

        while (stack.size() >= 2) {
            Pairs pop = stack.pop();
            Pairs prev = stack.peek();
            maxArea = Math.max(maxArea, pop.height * (i - prev.getIndex() - 1));
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 2};
//        int[] heights = {6, 7, 5, 2, 4, 5, 9, 3};
        Leetcode84V3 leetcode84 = new Leetcode84V3();
        System.out.println(leetcode84.largestRectangleArea(heights));
    }
}
